/*
 * Copyright (c) 2022 Huawei Device Co., Ltd.
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 *     http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */
import Unsafe from './Unsafe';
import { Table } from './FiniteStateEntropy'
import Huffman from './Huffman'
import XxHash64 from './XxHash64'
import FrameHeader from './FrameHeader'
import MalformedInputException from './MalformedInputException'
import Arrays from '../util/Arrays'
import FseTableReader from './FseTableReader'
import { Initializer, BitInputStream, Loader } from './BitInputStream'
import Constants from './Constants'
import Long from '../util/long/index'
import Util from './Util'

export default class ZstdFrameDecompressor {
    private static DEC_32_TABLE: Int32Array = new Int32Array([4, 1, 2, 1, 4, 4, 4, 4]);
    private static DEC_64_TABLE: Int32Array = new Int32Array([0, 0, 0, -1, 0, 1, 2, 3]);
    private static V07_MAGIC_NUMBER: number = -47205081;
    private static MAX_WINDOW_SIZE: number = 1 << 23;
    private static LITERALS_LENGTH_BASE: Int32Array = new Int32Array([
        0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15,
        16, 18, 20, 22, 24, 28, 32, 40, 48, 64, 0x80, 0x100, 0x200, 0x400, 0x800, 0x1000,
        0x2000, 0x4000, 0x8000, 0x10000]);
    private static MATCH_LENGTH_BASE: Int32Array = new Int32Array([
        3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18,
        19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34,
        35, 37, 39, 41, 43, 47, 51, 59, 67, 83, 99, 0x83, 0x103, 0x203, 0x403, 0x803,
        0x1003, 0x2003, 0x4003, 0x8003, 0x10003]);
    private static OFFSET_CODES_BASE: Int32Array = new Int32Array([
        0, 1, 1, 5, 0xD, 0x1D, 0x3D, 0x7D,
        0xFD, 0x1FD, 0x3FD, 0x7FD, 0xFFD, 0x1FFD, 0x3FFD, 0x7FFD,
        0xFFFD, 0x1FFFD, 0x3FFFD, 0x7FFFD, 0xFFFFD, 0x1FFFFD, 0x3FFFFD, 0x7FFFFD,
        0xFFFFFD, 0x1FFFFFD, 0x3FFFFFD, 0x7FFFFFD, 0xFFFFFFD]);
    private static DEFAULT_LITERALS_LENGTH_TABLE: Table = Table.getTable(
        6,
        new Int32Array([
            0, 16, 32, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 32, 0, 0, 0, 0, 32, 0, 0, 32, 0, 32, 0, 32, 0, 0, 32, 0, 32, 0, 32, 0, 0, 16, 32, 0, 0, 48, 16, 32, 32, 32,
            32, 32, 32, 32, 32, 0, 32, 32, 32, 32, 32, 32, 0, 0, 0, 0]),
        new Int8Array([
            0, 0, 1, 3, 4, 6, 7, 9, 10, 12, 14, 16, 18, 19, 21, 22, 24, 25, 26, 27, 29, 31, 0, 1, 2, 4, 5, 7, 8, 10, 11, 13, 16, 17, 19, 20, 22, 23, 25, 25, 26, 28, 30, 0,
            1, 2, 3, 5, 6, 8, 9, 11, 12, 15, 17, 18, 20, 21, 23, 24, 35, 34, 33, 32]),
        new Int8Array([4, 4, 5, 5, 5, 5, 5, 5, 5, 5, 6, 5, 5, 5, 5, 5, 5, 5, 5, 6, 6, 6, 4, 4, 5, 5, 5, 5, 5, 5, 5, 6, 5, 5, 5, 5, 5, 5, 4, 4, 5, 6, 6, 4, 4, 5, 5, 5, 5, 5, 5, 5, 5,
        6, 5, 5, 5, 5, 5, 5, 6, 6, 6, 6]));
    private static DEFAULT_OFFSET_CODES_TABLE: Table  = Table.getTable(
        5,
        new Int32Array([0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 16, 0, 0, 0, 0, 16, 0, 0, 0, 16, 0, 0, 0, 0, 0, 0, 0]),
        new Int8Array([0, 6, 9, 15, 21, 3, 7, 12, 18, 23, 5, 8, 14, 20, 2, 7, 11, 17, 22, 4, 8, 13, 19, 1, 6, 10, 16, 28, 27, 26, 25, 24]),
        new Int8Array([5, 4, 5, 5, 5, 5, 4, 5, 5, 5, 5, 4, 5, 5, 5, 4, 5, 5, 5, 5, 4, 5, 5, 5, 4, 5, 5, 5, 5, 5, 5, 5]));
    private static DEFAULT_MATCH_LENGTH_TABLE: Table = Table.getTable(
        6,
        new Int32Array([
            0, 0, 32, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 16, 0, 32, 0, 32, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 32, 48, 16, 32, 32, 32, 32,
            0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]),
        new Int8Array([
            0, 1, 2, 3, 5, 6, 8, 10, 13, 16, 19, 22, 25, 28, 31, 33, 35, 37, 39, 41, 43, 45, 1, 2, 3, 4, 6, 7, 9, 12, 15, 18, 21, 24, 27, 30, 32, 34, 36, 38, 40, 42, 44, 1,
            1, 2, 4, 5, 7, 8, 11, 14, 17, 20, 23, 26, 29, 52, 51, 50, 49, 48, 47, 46]),
        new Int8Array([
            6, 4, 5, 5, 5, 5, 5, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 4, 4, 5, 5, 5, 5, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 4, 4, 4, 5, 5, 5, 5, 6, 6, 6,
            6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6]));
    private literals: Int8Array = new Int8Array(Constants.MAX_BLOCK_SIZE + Constants.SIZE_OF_LONG); // extra space to allow for long-at-a-time copy

    private literalsBase;
    private literalsAddress: Long;
    private literalsLimit: Long;
    private previousOffsets: Int32Array= new Int32Array(3);
    private literalsLengthTable: Table= Table.getTables(Constants.LITERAL_LENGTH_TABLE_LOG);
    private offsetCodesTable: Table  = Table.getTables(Constants.OFFSET_TABLE_LOG);
    private matchLengthTable: Table = Table.getTables(Constants.MATCH_LENGTH_TABLE_LOG);
    private currentLiteralsLengthTable: Table;
    private currentOffsetCodesTable: Table;
    private currentMatchLengthTable: Table;
    private huffman: Huffman = new Huffman();
    private fse: FseTableReader = new FseTableReader();

    public decompress(
        inputBase: any,
        inputAddress: Long,
        inputLimit: Long,
        outputBase: object,
        outputAddress: Long,
        outputLimit: Long): number {
        if (outputAddress.eq(outputLimit)) {
            return 0;
        }

        let input: Long = inputAddress;
        let output: Long = outputAddress;

        while (input.lessThan(inputLimit)) {
            this.reset();
            let outputStart: Long = output;
            input = input.add(ZstdFrameDecompressor.verifyMagic(inputBase, inputAddress, inputLimit));

            let frameHeader: FrameHeader = ZstdFrameDecompressor.readFrameHeader(inputBase, input, inputLimit);
            input = input.add(frameHeader.headerSize);

            let lastBlock: boolean;
            do {
                Util.verify(input.add(Constants.SIZE_OF_BLOCK_HEADER)
                    .lessThanOrEqual(inputLimit), input, "Not enough input bytes");

                // read block header
                let header: number = Unsafe.getInt(inputBase, input.toNumber()) & 2097151;
                input = input.add(Constants.SIZE_OF_BLOCK_HEADER);

                lastBlock = (header & 1) != 0;
                let blockType: number = (header >>> 1) & 3;
                let blockSize: number = (header >>> 3) & 2097151; // 21 bits

                let decodedSize: number;
                switch (blockType) {
                    case Constants.RAW_BLOCK:
                        Util.verify(inputAddress.add(blockSize).lessThanOrEqual(inputLimit), input, "Not enough input bytes");
                        decodedSize = ZstdFrameDecompressor.decodeRawBlock(inputBase, input, blockSize, outputBase, output, outputLimit);
                        input = input.add(blockSize);
                        break;
                    case Constants.RLE_BLOCK:
                        Util.verify(inputAddress.add(1).lessThanOrEqual(inputLimit), input, "Not enough input bytes");
                        decodedSize = ZstdFrameDecompressor.decodeRleBlock(blockSize, inputBase, input, outputBase, output, outputLimit);
                        input = input.add(1);
                        break;
                    case Constants.COMPRESSED_BLOCK:
                        Util.verify(inputAddress.add(blockSize).lessThanOrEqual(inputLimit), input, "Not enough input bytes");
                        decodedSize = this.decodeCompressedBlock(inputBase, input, blockSize, outputBase, output, outputLimit, frameHeader.windowSize, outputAddress);
                        input = input.add(blockSize);
                        break;
                    default:
                        throw Util.fail(input, "Invalid block type");
                }

                output = output.add(decodedSize);
            } while (!lastBlock);

            if (frameHeader.hasChecksum) {
                let decodedFrameSize: number = output.sub(outputStart).toInt();

                let hash: Long = XxHash64.hash(Long.fromNumber(0), outputBase, outputStart, decodedFrameSize);

                let checksum: number = Unsafe.getInt(inputBase, input.toNumber());
                if (checksum != hash.toInt()) {
                    throw new MalformedInputException(input, "Bad checksum. Expected: %s, actual: %s"); //MalformedInputException(input, String.format("Bad checksum. Expected: %s, actual: %s", Integer.toHexString(checksum), Integer.toHexString((int) hash)));
                }
                input = input.add(Constants.SIZE_OF_INT);
            }
        }

        return output.sub(outputAddress).toInt();
    }

    private reset(): void {
        this.previousOffsets[0] = 1;
        this.previousOffsets[1] = 4;
        this.previousOffsets[2] = 8;

        this.currentLiteralsLengthTable = null;
        this.currentOffsetCodesTable = null;
        this.currentMatchLengthTable = null;
    }

    private static decodeRawBlock(inputBase: any, inputAddress: Long, blockSize: number, outputBase: any, outputAddress: Long, outputLimit: Long): number
    {
        Util.verify(outputAddress.add(blockSize).lessThanOrEqual(outputLimit), inputAddress, "Output buffer too small");

        Unsafe.copyMemory(inputBase, inputAddress.toNumber(), outputBase, outputAddress.toNumber(), Long.fromNumber(blockSize));
        return blockSize;
    }

    private static decodeRleBlock(size: number, inputBase, inputAddress: Long, outputBase, outputAddress: Long, outputLimit: Long): number
    {
        Util.verify(outputAddress.add(size).lessThanOrEqual(outputLimit), inputAddress, "Output buffer too small");

        let output: Long = outputAddress;
        let value: Long = Long.fromNumber(Unsafe.getByte(inputBase, inputAddress.toNumber()) & 0xFF);

        let remaining: number = size;
        if (remaining >= Constants.SIZE_OF_LONG) {
            let packed: Long = value
                .or(value.shiftLeft(8))
                .or(value.shiftLeft(16))
                .or(value.shiftLeft(24))
                .or(value.shiftLeft(32))
                .or(value.shiftLeft(40))
                .or(value.shiftLeft(48))
                .or(value.shiftLeft(56));

            do {
                Unsafe.putLong(outputBase, output.toNumber(), packed);
                output = output.add(Constants.SIZE_OF_LONG);
                remaining -= Constants.SIZE_OF_LONG;
            }
            while (remaining >= Constants.SIZE_OF_LONG);
        }

        for (let i: number = 0; i < remaining; i++) {
            Unsafe.putByte(outputBase, output.toNumber(), value.toNumber());
            output = output.add(1);
        }

        return size;
    }

    private decodeCompressedBlock(inputBase: any, inputAddress: Long, blockSize: number, outputBase: any, outputAddress: Long, outputLimit: Long, windowSize: number, outputAbsoluteBaseAddress: Long): number {
        let inputLimit: Long = inputAddress.add(blockSize);
        let input: Long = inputAddress;

        Util.verify(blockSize <= Constants.MAX_BLOCK_SIZE, input, "Expected match length table to be present");
        Util.verify(blockSize >= Constants.MIN_BLOCK_SIZE, input, "Compressed block size too small");

        let literalsBlockType: number = Unsafe.getByte(inputBase, input.toNumber()) & 3;

        switch (literalsBlockType) {
            case Constants.RAW_LITERALS_BLOCK:
            {
                input = input.add(this.decodeRawLiterals(inputBase, input, inputLimit));
                break;
            }
            case Constants.RLE_LITERALS_BLOCK:
            {
                input = input.add(this.decodeRleLiterals(inputBase, input, blockSize));
                break;
            }
            case Constants.TREELESS_LITERALS_BLOCK:
                Util.verify(this.huffman.isLoaded(), input, "Dictionary is corrupted");
            case Constants.COMPRESSED_LITERALS_BLOCK:
            {
                input = input.add(this.decodeCompressedLiterals(inputBase, input, blockSize, literalsBlockType));
                break;
            }
            default:
                throw Util.fail(input, "Invalid literals block encoding type");
        }

        Util.verify(windowSize <= ZstdFrameDecompressor.MAX_WINDOW_SIZE, input, "Window size too large (not yet supported)");

        return this.decompressSequences(
            inputBase, input, inputAddress.add(blockSize),
            outputBase, outputAddress, outputLimit,
            this.literalsBase, this.literalsAddress, this.literalsLimit,
            outputAbsoluteBaseAddress);
    }

    private decompressSequences(
        inputBase: any, inputAddress: Long, inputLimit: Long,
        outputBase: any, outputAddress: Long, outputLimit: Long,
        literalsBase: any, literalsAddress: Long, literalsLimit: Long,
        outputAbsoluteBaseAddress: Long): number
    {
        let fastOutputLimit: Long = outputLimit.sub(Constants.SIZE_OF_LONG);
        let fastMatchOutputLimit: Long = fastOutputLimit.sub(Constants.SIZE_OF_LONG);

        let input: Long = inputAddress;
        let output: Long = outputAddress;

        let literalsInput: Long = literalsAddress;

        let size: number = inputLimit.sub(inputAddress).toInt();
        Util.verify(size >= Constants.MIN_SEQUENCES_SIZE, input, "Not enough input bytes");

        let sequenceCount: number = Unsafe.getByte(inputBase, input.toNumber()) & 0xFF;
        input = input.add(1)
        if (sequenceCount != 0) {
            if (sequenceCount == 255) {
                Util.verify(input.add(Constants.SIZE_OF_SHORT).lessThanOrEqual(inputLimit), input, "Not enough input bytes");
                sequenceCount = (Unsafe.getShort(inputBase, input.toNumber()) & 0xFFFF) + Constants.LONG_NUMBER_OF_SEQUENCES;
                input = input.add(Constants.SIZE_OF_SHORT);
            }
            else if (sequenceCount > 127) {
                Util.verify(input < inputLimit, input, "Not enough input bytes");
                sequenceCount = ((sequenceCount - 128) << 8) + (Unsafe.getByte(inputBase, input.toNumber()) & 0xFF);
                input = input.add(1)
            }

            Util.verify(input.add(Constants.SIZE_OF_INT).lessThanOrEqual(inputLimit), input, "Not enough input bytes");
            let typeByte: number = Unsafe.getByte(inputBase, input.toNumber());
            input = input.add(1)

            let literalsLengthType: number = (typeByte & 0xFF) >>> 6;
            let offsetCodesType: number = (typeByte >>> 4) & 3;
            let matchLengthType: number = (typeByte >>> 2) & 3;

            input = this.computeLiteralsTable(literalsLengthType, inputBase, input, inputLimit);
            input = this.computeOffsetsTable(offsetCodesType, inputBase, input, inputLimit);
            input = this.computeMatchLengthTable(matchLengthType, inputBase, input, inputLimit);

            let initializer = new Initializer(inputBase, input, inputLimit);
            initializer.initialize();
            let bitsConsumed: number = initializer.getBitsConsumed();
            let bits: Long = initializer.getBits();
            let currentAddress: Long = initializer.getCurrentAddress();

            let currentLiteralsLengthTable: Table = this.currentLiteralsLengthTable;
            let currentOffsetCodesTable: Table = this.currentOffsetCodesTable;
            let currentMatchLengthTable: Table = this.currentMatchLengthTable;

            let literalsLengthState: number =
            BitInputStream.peekBits(bitsConsumed, bits, currentLiteralsLengthTable.log2Size)
                .toInt();
            bitsConsumed += currentLiteralsLengthTable.log2Size;

            let offsetCodesState: number = BitInputStream.peekBits(bitsConsumed, bits, currentOffsetCodesTable.log2Size)
                .toInt();
            bitsConsumed += currentOffsetCodesTable.log2Size;

            let matchLengthState: number = BitInputStream.peekBits(bitsConsumed, bits, currentMatchLengthTable.log2Size)
                .toInt();
            bitsConsumed += currentMatchLengthTable.log2Size;

            let previousOffsets: Int32Array = this.previousOffsets;

            let literalsLengthNumbersOfBits: Int8Array = currentLiteralsLengthTable.numberOfBits;
            let literalsLengthNewStates: Int32Array = currentLiteralsLengthTable.newState;
            let literalsLengthSymbols: Int8Array = currentLiteralsLengthTable.symbols;

            let matchLengthNumbersOfBits: Int8Array = currentMatchLengthTable.numberOfBits;
            let matchLengthNewStates: Int32Array = currentMatchLengthTable.newState;
            let matchLengthSymbols: Int8Array = currentMatchLengthTable.symbols;

            let offsetCodesNumbersOfBits: Int8Array = currentOffsetCodesTable.numberOfBits;
            let offsetCodesNewStates: Int32Array = currentOffsetCodesTable.newState;
            let offsetCodesSymbols: Int8Array = currentOffsetCodesTable.symbols;

            while (sequenceCount > 0) {
                sequenceCount--;

                let loader: Loader = new Loader(inputBase, input, currentAddress, bits, bitsConsumed);
                loader.load();
                bitsConsumed = loader.getBitsConsumed();
                bits = loader.getBits();
                currentAddress = loader.getCurrentAddress();
                if (loader.isOverflow()) {
                    Util.verify(sequenceCount == 0, input, "Not all sequences were consumed");
                    break;
                }

                let literalsLengthCode: number = literalsLengthSymbols[literalsLengthState];
                let matchLengthCode: number = matchLengthSymbols[matchLengthState];
                let offsetCode: number = offsetCodesSymbols[offsetCodesState];

                let literalsLengthBits: number = Constants.LITERALS_LENGTH_BITS[literalsLengthCode];
                let matchLengthBits: number = Constants.MATCH_LENGTH_BITS[matchLengthCode];
                let offsetBits: number = offsetCode;

                let offset: number = ZstdFrameDecompressor.OFFSET_CODES_BASE[offsetCode];
                if (offsetCode > 0) {
                    offset += BitInputStream.peekBits(bitsConsumed, bits, offsetBits).toInt();
                    bitsConsumed += offsetBits;
                }

                if (offsetCode <= 1) {
                    if (literalsLengthCode == 0) {
                        offset++;
                    }

                    if (offset != 0) {
                        let temp: number;
                        if (offset == 3) {
                            temp = previousOffsets[0] - 1;
                        }
                        else {
                            temp = previousOffsets[offset];
                        }

                        if (temp == 0) {
                            temp = 1;
                        }

                        if (offset != 1) {
                            previousOffsets[2] = previousOffsets[1];
                        }
                        previousOffsets[1] = previousOffsets[0];
                        previousOffsets[0] = temp;

                        offset = temp;
                    }
                    else {
                        offset = previousOffsets[0];
                    }
                }
                else {
                    previousOffsets[2] = previousOffsets[1];
                    previousOffsets[1] = previousOffsets[0];
                    previousOffsets[0] = offset;
                }

                let matchLength: number = ZstdFrameDecompressor.MATCH_LENGTH_BASE[matchLengthCode];
                if (matchLengthCode > 31) {
                    matchLength += BitInputStream.peekBits(bitsConsumed, bits, matchLengthBits).toInt();
                    bitsConsumed += matchLengthBits;
                }

                let literalsLength: number = ZstdFrameDecompressor.LITERALS_LENGTH_BASE[literalsLengthCode];
                if (literalsLengthCode > 15) {
                    literalsLength += BitInputStream.peekBits(bitsConsumed, bits, literalsLengthBits).toInt();
                    bitsConsumed += literalsLengthBits;
                }

                let totalBits: number = literalsLengthBits + matchLengthBits + offsetBits;
                if (totalBits > 64 - 7 - (Constants.LITERAL_LENGTH_TABLE_LOG + Constants.MATCH_LENGTH_TABLE_LOG + Constants.OFFSET_TABLE_LOG)) {
                    let loader1: Loader = new Loader(inputBase, input, currentAddress, bits, bitsConsumed);
                    loader1.load();

                    bitsConsumed = loader1.getBitsConsumed();
                    bits = loader1.getBits();
                    currentAddress = loader1.getCurrentAddress();
                }

                let numberOfBits: number;

                numberOfBits = literalsLengthNumbersOfBits[literalsLengthState];
                literalsLengthState = literalsLengthNewStates[literalsLengthState] +
                BitInputStream.peekBits(bitsConsumed, bits, numberOfBits)
                    .toInt(); // <= 9 bits
                bitsConsumed += numberOfBits;

                numberOfBits = matchLengthNumbersOfBits[matchLengthState];
                matchLengthState = matchLengthNewStates[matchLengthState] +
                BitInputStream.peekBits(bitsConsumed, bits, numberOfBits)
                    .toInt(); // <= 9 bits
                bitsConsumed += numberOfBits;

                numberOfBits = offsetCodesNumbersOfBits[offsetCodesState];
                offsetCodesState = offsetCodesNewStates[offsetCodesState] +
                BitInputStream.peekBits(bitsConsumed, bits, numberOfBits)
                    .toInt(); // <= 8 bits
                bitsConsumed += numberOfBits;

                let literalOutputLimit: Long = output.add(literalsLength);
                let matchOutputLimit: Long = literalOutputLimit.add(matchLength);

                Util.verify(matchOutputLimit.lessThanOrEqual(outputLimit), input, "Output buffer too small");
                let literalEnd: Long = literalsInput.add(literalsLength);
                Util.verify(literalEnd.lessThanOrEqual(literalsLimit), input, "Input is corrupted");

                let matchAddress: Long = literalOutputLimit.sub(offset);
                Util.verify(matchAddress.greaterThanOrEqual(outputAbsoluteBaseAddress), input, "Input is corrupted");

                if (literalOutputLimit.greaterThan(fastOutputLimit)) {
                    this.executeLastSequence(outputBase, output, literalOutputLimit, matchOutputLimit, fastOutputLimit, literalsInput, matchAddress);
                }
                else {
                    output = this.copyLiterals(outputBase, literalsBase, output, literalsInput, literalOutputLimit);
                    this.copyMatch(outputBase, fastOutputLimit, output, offset, matchOutputLimit, matchAddress, matchLength, fastMatchOutputLimit);
                }
                output = matchOutputLimit;
                literalsInput = literalEnd;
            }
        }

        output = this.copyLastLiteral(outputBase, literalsBase, literalsLimit, output, literalsInput);

        return output.sub(outputAddress).toInt();
    }

    private copyLastLiteral(outputBase: any, literalsBase: any, literalsLimit: Long, output: Long, literalsInput: Long): Long {
        let lastLiteralsSize: Long = literalsLimit.sub(literalsInput);
        Unsafe.copyMemory(literalsBase, literalsInput.toNumber(), outputBase, output.toNumber(), lastLiteralsSize);
        output = output.add(lastLiteralsSize);
        return output;
    }

    private copyMatch(outputBase: any, fastOutputLimit: Long, output: Long, offset: number, matchOutputLimit: Long, matchAddress: Long, matchLength: number, fastMatchOutputLimit: Long): void {
        matchAddress = this.copyMatchHead(outputBase, output, offset, matchAddress);
        output = output.add(Constants.SIZE_OF_LONG);
        matchLength -= Constants.SIZE_OF_LONG; // first 8 bytes copied above
        this.copyMatchTail(outputBase, fastOutputLimit, output, matchOutputLimit, matchAddress, matchLength, fastMatchOutputLimit);
    }

    private copyMatchTail(outputBase: any, fastOutputLimit: Long, output: Long, matchOutputLimit: Long, matchAddress: Long, matchLength: number, fastMatchOutputLimit: Long): void {
        if (matchOutputLimit.lessThan(fastMatchOutputLimit)) {
            let copied: number = 0;
            do {
                Unsafe.putLong(outputBase, output.toNumber(), Unsafe.getLong(outputBase, matchAddress.toNumber()));
                output = output.add(Constants.SIZE_OF_LONG);
                matchAddress = matchAddress.add(Constants.SIZE_OF_LONG);
                copied += Constants.SIZE_OF_LONG;
            }
            while (copied < matchLength);
        }
        else {
            while (output.lessThan(fastOutputLimit)) {
                Unsafe.putLong(outputBase, output.toNumber(), Unsafe.getLong(outputBase, matchAddress.toNumber()));
                matchAddress = matchAddress.add(Constants.SIZE_OF_LONG);
                output = output.add(Constants.SIZE_OF_LONG);
            }

            while (output.lessThan(matchOutputLimit)) {
                let getBytes = Unsafe.getByte(outputBase, matchAddress.toNumber())
                matchAddress = matchAddress.add(1)
                Unsafe.putByte(outputBase, output.toNumber(), getBytes);
                output = output.add(1)
            }
        }
    }

    private copyMatchHead(outputBase: Array<any>, output: Long, offset: number, matchAddress: Long): Long
    {
        if (offset < 8) {
            let increment32: number = ZstdFrameDecompressor.DEC_32_TABLE[offset];
            let decrement64: number = ZstdFrameDecompressor.DEC_64_TABLE[offset];

            Unsafe.putByte(outputBase, output.toNumber(), Unsafe.getByte(outputBase, matchAddress.toNumber()));
            Unsafe.putByte(outputBase, output.toNumber() + 1, Unsafe.getByte(outputBase, matchAddress.toNumber() + 1));
            Unsafe.putByte(outputBase, output.toNumber() + 2, Unsafe.getByte(outputBase, matchAddress.toNumber() + 2));
            Unsafe.putByte(outputBase, output.toNumber() + 3, Unsafe.getByte(outputBase, matchAddress.toNumber() + 3));
            matchAddress = matchAddress.add(increment32);

            Unsafe.putInt(outputBase, output.toNumber() + 4, Unsafe.getInt(outputBase, matchAddress.toNumber()));
            matchAddress = matchAddress.sub(decrement64);
        }
        else {
            Unsafe.putLong(outputBase, output.toNumber(), Unsafe.getLong(outputBase, matchAddress.toNumber()));
            matchAddress = matchAddress.add(Constants.SIZE_OF_LONG);
        }
        return matchAddress;
    }

    private copyLiterals(outputBase, literalsBase, output: Long, literalsInput: Long, literalOutputLimit: Long): Long
    {
        let literalInput: Long = literalsInput;
        do {
            Unsafe.putLong(outputBase, output.toNumber(), Unsafe.getLong(literalsBase, literalInput.toNumber()));
            output = output.add(Constants.SIZE_OF_LONG);
            literalInput = literalInput.add(Constants.SIZE_OF_LONG);
        }
        while (output.lessThan(literalOutputLimit));
        output = literalOutputLimit; // correction in case we over-copied
        return output;
    }

    private computeMatchLengthTable(matchLengthType: number, inputBase, input: Long, inputLimit: Long): Long
    {
        switch (matchLengthType) {
            case Constants.SEQUENCE_ENCODING_RLE:
                Util.verify(input.lessThan(inputLimit), input, "Not enough input bytes");

                let value: number = Unsafe.getByte(inputBase, input.toNumber());
                input = input.add(1)
                Util.verify(value <= Constants.MAX_MATCH_LENGTH_SYMBOL, input, "Value exceeds expected maximum value");

                FseTableReader.initializeRleTable(this.matchLengthTable, value);
                this.currentMatchLengthTable = this.matchLengthTable;
                break;
            case Constants.SEQUENCE_ENCODING_BASIC:
                this.currentMatchLengthTable = ZstdFrameDecompressor.DEFAULT_MATCH_LENGTH_TABLE;
                break;
            case Constants.SEQUENCE_ENCODING_REPEAT:
                Util.verify(this.currentMatchLengthTable != null, input, "Expected match length table to be present");
                break;
            case Constants.SEQUENCE_ENCODING_COMPRESSED:
                input = input.add(this.fse.readFseTable(this.matchLengthTable, inputBase, input, inputLimit, Constants.MAX_MATCH_LENGTH_SYMBOL, Constants.MATCH_LENGTH_TABLE_LOG));
                this.currentMatchLengthTable = this.matchLengthTable;
                break;
            default:
                throw Util.fail(input, "Invalid match length encoding type");
        }
        return input;
    }

    private computeOffsetsTable(offsetCodesType: number, inputBase: any, input: Long, inputLimit: Long): Long
    {
        switch (offsetCodesType) {
            case Constants.SEQUENCE_ENCODING_RLE:
                Util.verify(input.lessThan(inputLimit), input, "Not enough input bytes");

                let value: number = Unsafe.getByte(inputBase, input.toNumber());
                input = input.add(1)
                Util.verify(value <= Constants.DEFAULT_MAX_OFFSET_CODE_SYMBOL, input, "Value exceeds expected maximum value");

                FseTableReader.initializeRleTable(this.offsetCodesTable, value);
                this.currentOffsetCodesTable = this.offsetCodesTable;
                break;
            case Constants.SEQUENCE_ENCODING_BASIC:
                this.currentOffsetCodesTable = ZstdFrameDecompressor.DEFAULT_OFFSET_CODES_TABLE;
                break;
            case Constants.SEQUENCE_ENCODING_REPEAT:
                Util.verify(this.currentOffsetCodesTable != null, input, "Expected match length table to be present");
                break;
            case Constants.SEQUENCE_ENCODING_COMPRESSED:
                input = input.add(this.fse.readFseTable(this.offsetCodesTable, inputBase, input, inputLimit, Constants.DEFAULT_MAX_OFFSET_CODE_SYMBOL, Constants.OFFSET_TABLE_LOG));
                this.currentOffsetCodesTable = this.offsetCodesTable;
                break;
            default:
                throw Util.fail(input, "Invalid offset code encoding type");
        }
        return input;
    }

    private computeLiteralsTable(literalsLengthType: number, inputBase, input: Long, inputLimit: Long): Long
    {
        switch (literalsLengthType) {
            case Constants.SEQUENCE_ENCODING_RLE:
                Util.verify(input.lessThan(inputLimit), input, "Not enough input bytes");

                let value: number = Unsafe.getByte(inputBase, input.toNumber());
                input = input.add(1)
                Util.verify(value <= Constants.MAX_LITERALS_LENGTH_SYMBOL, input, "Value exceeds expected maximum value");

                FseTableReader.initializeRleTable(this.literalsLengthTable, value);
                this.currentLiteralsLengthTable = this.literalsLengthTable;
                break;
            case Constants.SEQUENCE_ENCODING_BASIC:
                this.currentLiteralsLengthTable = ZstdFrameDecompressor.DEFAULT_LITERALS_LENGTH_TABLE;
                break;
            case Constants.SEQUENCE_ENCODING_REPEAT:
                Util.verify(this.currentLiteralsLengthTable != null, input, "Expected match length table to be present");
                break;
            case Constants.SEQUENCE_ENCODING_COMPRESSED:
                input = input.add(this.fse.readFseTable(this.literalsLengthTable, inputBase, input, inputLimit, Constants.MAX_LITERALS_LENGTH_SYMBOL, Constants.LITERAL_LENGTH_TABLE_LOG));
                this.currentLiteralsLengthTable = this.literalsLengthTable;
                break;
            default:
                throw Util.fail(input, "Invalid literals length encoding type");
        }
        return input;
    }

    private executeLastSequence(outputBase, output: Long, literalOutputLimit: Long, matchOutputLimit: Long, fastOutputLimit: Long, literalInput: Long, matchAddress: Long): void {
        if (output.lessThan(fastOutputLimit)) {
            do {
                Unsafe.putLong(outputBase, output.toNumber(), Unsafe.getLong(this.literalsBase, literalInput.toNumber()));
                output = output.add(Constants.SIZE_OF_LONG);
                literalInput = literalInput.add(Constants.SIZE_OF_LONG);
            }
            while (output.lessThan(fastOutputLimit));

            literalInput = literalInput.sub(output.sub(fastOutputLimit));
            output = fastOutputLimit;
        }

        while (output.lessThan(literalOutputLimit)) {
            Unsafe.putByte(outputBase, output.toNumber(), Unsafe.getByte(this.literalsBase, literalInput.toNumber()));
            output = output.add(1);
            literalInput = literalInput.add(1);
        }

        while (output.lessThan(matchOutputLimit)) {
            Unsafe.putByte(outputBase, output.toNumber(), Unsafe.getByte(outputBase, matchAddress.toNumber()));
            output = output.add(1);
            matchAddress = matchAddress.add(1);
        }
    }

    private decodeCompressedLiterals(inputBase: any, inputAddress: Long, blockSize: number, literalsBlockType: number): number {
        let input: Long = inputAddress;
        Util.verify(blockSize >= 5, input, "Not enough input bytes");

        let compressedSize: number;
        let uncompressedSize: number;
        let singleStream: boolean = false;
        let headerSize: number;
        let typeInt: number = (Unsafe.getByte(inputBase, input.toNumber()) >> 2) & 0b11;
        switch (typeInt) {
            case 0:
                singleStream = true;
            case 1:
            {
                let header: number = Unsafe.getInt(inputBase, input.toNumber());
                headerSize = 3;
                uncompressedSize = (header >>> 4) & Util.mask(10);
                compressedSize = (header >>> 14) & Util.mask(10);
                break;
            }
            case 2:
            {
                let header: number = Unsafe.getInt(inputBase, input.toNumber());
                headerSize = 4;
                uncompressedSize = (header >>> 4) & Util.mask(14);
                compressedSize = (header >>> 18) & Util.mask(14);
                break;
            }
            case 3:
            {
                let header: Long = Long.fromNumber(Unsafe.getByte(inputBase, input.toNumber()))
                    .and(255)
                    .or(Long.fromNumber(Unsafe.getInt(inputBase, input.add(1).toNumber())).and(4294967295)
                        .shiftLeft(8));

                headerSize = 5;
                uncompressedSize = header.shiftRightUnsigned(4).and(Util.mask(18)).toInt();
                compressedSize = header.shiftRightUnsigned(22).and(Util.mask(18)).toInt();
                break;
            }
            default:
                throw Util.fail(input, "Invalid literals header size type");
        }

        Util.verify(uncompressedSize <= Constants.MAX_BLOCK_SIZE, input, "Block exceeds maximum size");
        Util.verify(headerSize + compressedSize <= blockSize, input, "Input is corrupted");

        input = input.add(headerSize);

        let inputLimit: Long = input.add(compressedSize);
        if (literalsBlockType != Constants.TREELESS_LITERALS_BLOCK) {
            input = input.add(this.huffman.readTable(inputBase, input, compressedSize));
        }

        this.literalsBase = this.literals;
        this.literalsAddress = Long.fromNumber(Unsafe.ARRAY_BYTE_BASE_OFFSET);
        this.literalsLimit = Long.fromNumber(Unsafe.ARRAY_BYTE_BASE_OFFSET + uncompressedSize);

        if (singleStream) {
            this.huffman.decodeSingleStream(inputBase, input, inputLimit, this.literals, this.literalsAddress, this.literalsLimit);
        }
        else {
            this.huffman.decode4Streams(inputBase, input, inputLimit, this.literals, this.literalsAddress, this.literalsLimit);
        }

        return headerSize + compressedSize;
    }

    private decodeRleLiterals(inputBase, inputAddress: Long, blockSize: number): number {
        let input: Long = inputAddress;
        let outputSize: number;
        let typeInt: number = (Unsafe.getByte(inputBase, input.toNumber()) >> 2) & 3;
        switch (typeInt) {
            case 0:
            case 2:
                outputSize = (Unsafe.getByte(inputBase, input.toNumber()) & 0xFF) >>> 3;
                input = input.add(1);
                break;
            case 1:
                outputSize = (Unsafe.getShort(inputBase, input.toNumber()) & 0xFFFF) >>> 4;
                input = input.add(2);
                break;
            case 3:
                Util.verify(blockSize >= Constants.SIZE_OF_INT, input, "Not enough input bytes");
                outputSize = (Unsafe.getInt(inputBase, input.toNumber()) & 16777215) >>> 4;
                input = input.add(3);
                break;
            default:
                throw Util.fail(input, "Invalid RLE literals header encoding type");
        }

        Util.verify(outputSize <= Constants.MAX_BLOCK_SIZE, input, "Output exceeds maximum block size");
        let value: number = Unsafe.getByte(inputBase, input.toNumber());
        input = input.add(1)
        Arrays.fillByte(this.literals, 0, outputSize + Constants.SIZE_OF_LONG, value);

        this.literalsBase = this.literals;
        this.literalsAddress = Long.fromNumber(Unsafe.ARRAY_BYTE_BASE_OFFSET);
        this.literalsLimit = Long.fromNumber(Unsafe.ARRAY_BYTE_BASE_OFFSET + outputSize);

        return input.sub(inputAddress).toInt();
    }

    private decodeRawLiterals(inputBase, inputAddress: Long, inputLimit: Long): number
    {
        let input: Long = inputAddress;
        let typeInt: number = (Unsafe.getByte(inputBase, input.toNumber()) >> 2) & 3;

        let literalSize: number;
        switch (typeInt) {
            case 0:
            case 2:
                literalSize = (Unsafe.getByte(inputBase, input.toNumber()) & 0xFF) >>> 3;
                input = input.add(1);
                break;
            case 1:
                literalSize = (Unsafe.getShort(inputBase, input.toNumber()) & 0xFFFF) >>> 4;
                input = input.add(2);
                break;
            case 3:
                let header: number = ((Unsafe.getByte(inputBase, input.toNumber()) & 0xFF) |
                ((Unsafe.getShort(inputBase, input.add(1).toNumber()) & 0xFFFF) << 8));

                literalSize = header >>> 4;
                input = input.add(3);
                break;
            default:
                throw Util.fail(input, "Invalid raw literals header encoding type");
        }

        Util.verify(input.add(literalSize).lessThanOrEqual(inputLimit), input, "Not enough input bytes");
        if (Long.fromNumber(literalSize).greaterThan(inputLimit.sub(input).sub(Constants.SIZE_OF_LONG))) {
            this.literalsBase = this.literals;
            this.literalsAddress = Long.fromNumber(Unsafe.ARRAY_BYTE_BASE_OFFSET);
            this.literalsLimit = Long.fromNumber(Unsafe.ARRAY_BYTE_BASE_OFFSET + literalSize);

            Unsafe.copyMemory(inputBase, input.toNumber(), this.literals, this.literalsAddress.toNumber(), Long.fromNumber(literalSize));
            Arrays.fillByte(this.literals, literalSize, literalSize + Constants.SIZE_OF_LONG, 0);
        }
        else {
            this.literalsBase = inputBase;
            this.literalsAddress = input;
            this.literalsLimit = this.literalsAddress.add(literalSize);
        }
        input = input.add(literalSize);

        return input.sub(inputAddress).toInt();
    }

    static readFrameHeader(inputBase, inputAddress: Long, inputLimit: Long): FrameHeader {
        let input: Long = inputAddress;
        Util.verify(input.lessThan(inputLimit), input, "Not enough input bytes");
        let frameHeaderDescriptor: number = Unsafe.getByte(inputBase, input.toNumber()) & 0xFF;
        input = input.add(1)
        let singleSegment: boolean = (frameHeaderDescriptor & 32) != 0;
        let dictionaryDescriptor: number = frameHeaderDescriptor & 3;
        let contentSizeDescriptor: number = frameHeaderDescriptor >>> 6;

        let headerSize: number = 1 +
        (singleSegment ? 0 : 1) +
        (dictionaryDescriptor == 0 ? 0 : (1 << (dictionaryDescriptor - 1))) +
        (contentSizeDescriptor == 0 ? (singleSegment ? 1 : 0) : (1 << contentSizeDescriptor));

        Util.verify(Long.fromNumber(headerSize)
            .lessThanOrEqual(inputLimit.sub(inputAddress)), input, "Not enough input bytes");
        let windowSize: number = -1;
        if (!singleSegment) {
            let windowDescriptor: number = Unsafe.getByte(inputBase, input.toNumber()) & 0xFF;
            input = input.add(1)
            let exponent: number = windowDescriptor >>> 3;
            let mantissa: number = windowDescriptor & 7;

            let base: number = 1 << (Constants.MIN_WINDOW_LOG + exponent);
            windowSize = base + (base / 8) * mantissa;
        }

        let dictionaryId: Long = Long.fromNumber(-1);
        switch (dictionaryDescriptor) {
            case 1:
                dictionaryId = Long.fromNumber(Unsafe.getByte(inputBase, input.toNumber()) & 0xFF);
                input = input.add(Constants.SIZE_OF_BYTE);
                break;
            case 2:
                dictionaryId = Long.fromNumber(Unsafe.getShort(inputBase, input.toNumber()) & 0xFFFF);
                input = input.add(Constants.SIZE_OF_SHORT);
                break;
            case 3:
                dictionaryId = Long.fromNumber(Unsafe.getInt(inputBase, input.toNumber())).and(Long.fromString('4294967295'));
                input = input.add(Constants.SIZE_OF_INT);
                break;
        }
        Util.verify(dictionaryId.eq(-1), input, "Custom dictionaries not supported");

        let contentSize: Long = Long.fromNumber(-1);
        switch (contentSizeDescriptor) {
            case 0:
                if (singleSegment) {
                    contentSize = Long.fromNumber(Unsafe.getByte(inputBase, input.toNumber()) & 0xFF);
                    input = input.add(Constants.SIZE_OF_BYTE);
                }
                break;
            case 1:
                contentSize = Long.fromNumber(Unsafe.getShort(inputBase, input.toNumber()) & 0xFFFF);
                contentSize = contentSize.add(256);
                input = input.add(Constants.SIZE_OF_SHORT);
                break;
            case 2:
                contentSize = Long.fromNumber(Unsafe.getInt(inputBase, input.toNumber())).and(Long.fromString('4294967295'));
                input = input.add(Constants.SIZE_OF_INT);
                break;
            case 3:
                contentSize = Unsafe.getLong(inputBase, input.toNumber());
                input = input.add(Constants.SIZE_OF_LONG);
                break;
        }

        let hasChecksum: boolean = (frameHeaderDescriptor & 0b100) != 0;

        return new FrameHeader(
        input.sub(inputAddress),
            windowSize,
            contentSize,
            dictionaryId,
            hasChecksum);
    }

    public static getDecompressedSize(inputBase: object, inputAddress: Long, inputLimit: Long): Long {
        let input: Long = inputAddress;
        input = input.add(ZstdFrameDecompressor.verifyMagic(inputBase, input, inputLimit));
        return ZstdFrameDecompressor.readFrameHeader(inputBase, input, inputLimit).contentSize;
    }

    static verifyMagic(inputBase, inputAddress: Long, inputLimit: Long): number{
        Util.verify(inputLimit.sub(inputAddress).greaterThanOrEqual(4), inputAddress, "Not enough input bytes");

        let magic: number = Unsafe.getInt(inputBase, inputAddress.toNumber());
        if (magic != Constants.MAGIC_NUMBER) {
            if (magic == ZstdFrameDecompressor.V07_MAGIC_NUMBER) {
                throw new MalformedInputException(inputAddress, "Data encoded in unsupported ZSTD v0.7 format");
            }
            throw new MalformedInputException(inputAddress, "Invalid magic prefix ");
        }

        return Constants.SIZE_OF_INT;
    }
}

